1. Technical Field
The present invention relates to memory controllers, and more particularly to the reordering of data responses.
2. Discussion of Related Art
A memory controller 101 of a deterministic memory system 102 receives data back from the memory in the same order as the transactions' issuing order (see FIG. 1). This can lower the memory bandwidth utilization and increase the read latency of transactions. Both these characteristics can be improved if the return data is allowed to return out of issuing order.
Referring to FIG. 2, the point-to-point links between the memory controller 101 and the memory modules 201 and between the memory modules are split into two uni-directional buses; one for read traffic 202 and another for write and command traffic 203. The memory controller 101 comprises of an issue queue 204 from which commands to the memory modules 201 are issued. Read requests are moved from the issue queue to a response queue 205 once the request has been sent out to the memory module. Note architectures with unified issue and response queue can also be used. The function of the response queue 205 is to associate the returning read data with the appropriate read request. Read requests 206 are associated with IDs 207, also referred to as transaction IDs, which are used by the requesting component to identify the read requests.
Due to use of the daisy chain, the distance of a memory module from a particular memory controller is a function of the distance of the memory module from the memory controller. Thus, memory transactions addressed to two different memory modules would want to start using the return data bus at two different times. There could however be some overlap in the times that they request the bus.
The FIG. 3 depicts the usage of the return data link in the system which is closest to the memory controller from the current scheduling instant, represented as T0, to the last instant at which a transaction that is scheduled at T0 can use the link, W1. Filled red slots are used to identify periods when the link is utilized by returning read data. Free slots are marked by blank spaces. W0 is the earliest that a read transaction will require this link, while W1 is the latest that a transaction will require the link. Typically, W0 corresponds to the time at which a read data from the first memory module in the daisy chain would start using the link and W1 corresponds to the instant at which a memory request to the last memory module in the chain would complete using this link. A red line marks the completion time of the last transaction to use the link.
Current existing solutions permit the return data to return in the same order that the commands are issued in. In order to enforce this and ensure that returning data does not conflict on the link, the memory controller tracks the last usage of the return link. This information is tracked by using a single register or counter. The memory controller uses this register to determine if the return data link is available for scheduling the next memory read request. Upon scheduling a read request, this register is updated.
In-order return requires that the memory controller schedule only transactions that return read data after the completion of the last transaction. As seen in FIG. 3, this approach results in the scheduler having to forgo many opportunities prior to the completion of last read data return.
If the memory controller permitted read data out-of-order (i.e. in a different order from that in which the requests were sent out), the memory controller could use the idle gaps in the scheduling window prior to the start of the last read transaction data burst. This would require that the memory controller track all the busy times which fall within the scheduling window, W0 and W1.
In such a system the memory controller maintains a FIFO response queue, i.e., a queue with read transactions that have already been issued to the memory modules and are in the process of returning data. The queue can be implemented in several different ways. One such implementation is shown in FIG. 4. As seen in FIG. 4 all read transactions that are issued are enqueued at the tail and all returning read data is associated with the head entry.
In-order return of read data lowers the bandwidth utilization and increases the latency in a memory system that uses point-to-point interconnect.
To permit memory data to return in a different order from which it is issued, a mechanism should be provided to allow the memory controller to be able to associate the return data with the appropriate read data. One such approach would be to insert tags with each return data to identify the ordering. This mechanism would require the memory controller to generate and monitor tags. The protocol would nave to be modified to incorporate tags. The response queue would have to be modified to allow tag matching. The response queue would have to be modified to permit data to return. FIG. 5 depicts a possible implementation for such an approach. Read data is associated with a tag which is used to perform a look up in the response queue. The associated transaction information is read out when there is a tag match.
The disadvantage of using read data tags is that the memory controller would require additional logic to generate track and maintain the tags. Further, tags would have to be associated with all read data and this would lower the available bandwidth to transmit read data.
Therefore, a need exists for a memory controller for reordering of data responses.